package com.dubious.interview.euler;

import java.math.BigInteger;

import org.joda.time.DateTime;

public class Problem15 {

    /**
     * Starting in the top left corner of a 2x2 grid, there are 6 routes (without backtracking) to
     * the bottom right corner.
     * 
     * How many routes are there through a 20x20 grid?
     * 
     * @param args
     */
    public static void main(String[] args) {
        //@formatter:off
        // this problem screams for dynamic programming
        // an n x n grid has, actually (n + 1) * (n + 1) vertices
        //@formatter:on

        System.out.println("Start Time: " + new DateTime());

        int n = 20;
        long[][] gridVertices = new long[n + 1][n + 1];

        gridVertices[0][0] = 1;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 && j == 0) {
                    gridVertices[i][j] = 1;
                } else {
                    gridVertices[i][j] = 0;
                }
                if (i > 0) {
                    gridVertices[i][j] += gridVertices[i - 1][j];
                }
                if (j > 0) {
                    gridVertices[i][j] += gridVertices[i][j - 1];
                }
            }
        }

        System.out.println("Paths for 20x20 grid: " + gridVertices[n][n]);
        // 137846528820
        System.out.println("End Time: " + new DateTime());
        // 94 ms

        //@formatter:off
        // NOTE
        // apparently it can be solved using a mathematical equation.  something combinatorial.
        // it's pascal's triangle - use m C r = m!/(r!(m-r)!)
        // where m is the "row" and r is the "column" in the row.  in our case m = n^2 and r is n
        //@formatter:on

        BigInteger factorialN = factorial(n * 2);
        BigInteger factorialNd2 = factorial((n));
        System.out.println("factorial dividend: " + factorialN);
        System.out.println("factorial divisor: " + factorialNd2);

        BigInteger numPaths = factorialN.divide(factorialNd2).divide(factorialNd2);
        System.out.println("Paths using factorial " + numPaths);
        System.out.println("New End Time: " + new DateTime());
        // 1 ms
    }

    public static BigInteger factorial(int n) {
        BigInteger factorial = BigInteger.ONE;
        for (int i = 1; i <= n; i++) {
            factorial = factorial.multiply(BigInteger.valueOf(i));
        }

        return factorial;
    }
}
